package basic_practice_1005;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		List<Integer>  Fibonacci=new ArrayList<>();
		Fibonacci.add(1);
		Fibonacci.add(2);
		Fibonacci.add(3);
		Fibonacci.add(5);
		
		int flag=-1;

		Scanner scanner=new Scanner(System.in);
		
		while(scanner.hasNext()) {
			int n=scanner.nextInt();
			while(n>=Fibonacci.size()) {
				int fib=Fibonacci.get(Fibonacci.size()-2)+Fibonacci.get(Fibonacci.size()-1);
				if(flag<0&&fib>=1000000) {
					flag=Fibonacci.size();
				}
				fib=fib%1000000;
				Fibonacci.add(fib);
			}
			String out=""+Fibonacci.get(n-1);
			if(n>flag&&flag>=0) {
				while(out.length()<6) {
					out="0"+out;
				}
			}
			System.out.println(out);
		}
		
		scanner.close();
	}
}
